Flash-based storage media, such as solid-state drives (SSDs), comprise flash cells arranged in units of planes, blocks, and pages. Each plane contains a number of blocks, which are the smallest unit that can be erased. Each block contains a number of pages, which are the smallest unit that can be written with data. Within an SSD, a memory controller is responsible for mapping the logical block addresses of application data to be written to or read from the physical flash pages. Application data may be in the form of objects, such as a document, an image, a multimedia file, etc.
FIG. 1 is a block diagram of a host device 100 storing data objects 104, 106, 108, and 110 in a storage device 102, according to the prior art. The storage device 102 is a flash-based device, such as an SSD. As shown in FIG. 1, the host device 100 has one or more software applications simultaneously writing objects 104, 106, 108, and 110 to the storage device 102. When multiple objects 104, 106, 108, and 110 are being written to the storage device 102 simultaneously (i.e. in parallel) by an application or applications running on the host device 100, the chunks of data 104a-e, 106a-e, 108a-e, and 110a-e that make up the objects 104, 106, 108, and 110, respectively, become blended with other chunks corresponding to the other objects, resulting in fragmentation of the data when it is stored in blocks 101, 103, 105, and 107 of the storage device 102.
In other words, as shown in FIG. 1, different chunks of data 104a-e, 106a-e, 108a-e, and 110a-e for the various objects will end up being stored in the same block 101, 103, 105, or 107 within the storage device 102. Subsequently, when an application deletes an object, such as object 104, the corresponding pages storing objects 104a-e will need to be invalidated (denoted by an “x” in FIG. 1) from the various blocks 101, 103, 105, and 107. The blocks 101, 103, 105, and 107 become heavily fragmented, containing both valid and invalid pages of data, and require garbage collection to copy the invalid pages into other blocks containing only valid pages in order for the remaining block with invalid pages to be completely erased to form a fresh, re-useable block.
The heavy fragmentation of the blocks, and the accompanying garbage collection that is needed to clear invalid pages, results in increased write amplification (the ratio of data written by the flash memory of the storage device 102 compared to the data requested to be written by the host device 100) and significantly degrades the performance of the storage device 102.
What is needed, therefore, is an improved scheme for storing data in a flash-based storage device that minimizes the fragmentation of the storage device's blocks, reducing write amplification and increasing the performance of the storage device.